|
In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other. ==Algorithmic complexity== gives an O(''n''2)-time algorithm that tests whether a given ''n''-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. A number of other problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs. For instance, showed that the treewidth of a circle graph can be determined, and an optimal tree decomposition constructed, in O(''n''3) time. Additionally, a minimum fill-in (that is, a chordal graph with as few edges as possible that contains the given circle graph as a subgraph) may be found in O(''n''3) time.〔.〕 has shown that a maximum clique of a circle graph can be found in O(''n'' log2 ''n'') time, while have shown that a maximum independent set of an unweighted circle graph can be found in O(''n'' min) time, where ''d'' is a parameter of the graph known as its density, and ''α'' is the independence number of the circle graph. However, there are also problems that remain NP-complete when restricted to circle graphs. These include the minimum dominating set, minimum connected dominating set, and minimum total dominating set problems. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Circle graph」の詳細全文を読む スポンサード リンク
|